#include <iostream>
#include <vector>

using namespace std;

// 图的邻接表表示
class Graph {
private:
    int V; // 顶点数
    vector<int> *adj; // 邻接表

public:
    Graph(int V); // 构造函数
    void addEdge(int v, int w); // 添加边
    void DFS(int v); // 深度优先搜索
    void DFSUtil(int v, bool visited[]); // 辅助函数，用于递归DFS
};

// 构造函数
Graph::Graph(int V) {
    this->V = V + 1; // 因为顶点编号从1开始，所以需要V+1个空间
    adj = new vector<int>[V + 1];
}

// 添加边
void Graph::addEdge(int v, int w) {
    adj[v].push_back(w); // 添加w到v的邻接表
    adj[w].push_back(v); // 由于是无向图，也需要添加v到w的邻接表
}

// 深度优先搜索
void Graph::DFS(int v) {
    bool *visited = new bool[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }
    DFSUtil(v, visited);
}

// 辅助函数，用于递归DFS
void Graph::DFSUtil(int v, bool visited[]) {
    visited[v] = true;
    cout << v << " ";

    // 遍历所有邻接顶点
    for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i]) {
            DFSUtil(*i, visited);
        }
    }
}

int main() {
    int V, E;
    cout << "请输入顶点的个数: ";
    cin >> V;

    // 创建一个有V个顶点的图，顶点编号为1到V
    Graph g(V);

    cout << "请输入边的数量: ";
    cin >> E;

    cout << "请输入每条边的两个顶点 (格式: v w):" << endl;
    for (int i = 0; i < E; i++) {
        int v, w;
        cin >> v >> w;
        g.addEdge(v, w);
    }

    int startVertex;
    cout << "请输入深度优先搜索的起始顶点: ";
    cin >> startVertex;

    cout << "深度优先搜索遍历 (从顶点 " << startVertex << " 开始): ";
    g.DFS(startVertex);
    cout << endl;

    return 0;
}